Course / training:

Method for Logical Analysis

Combinatorische explosie in Logische systemen



Syntactische expansie.




5.

 

Syntactische variatie bij symmetrische connectieven - tot diepteniveau twee.



(5.1)

Structuurvariatie bij symmetrische connectieven, tot diepteniveau twee.


Een efficiënte vorm voor een redenering met symmetrisch connectief is die in standaard normaalvorm: conjunctief normaal vorm (

CNF

); of disjunctief normaal vorm (

DNF

). Kenmerkend voor zulke formules is dat ze maximaal twee nestingniveaus of 'etages' hebben.
Wanneer we van redeneervormen van deelverzamelingen van

U

·(v,d) structuurvarianten construeren die in normaalvorm staan, zullen hun diepteniveaus dus in principe beperkt blijven tot hoogstens twee.

tc*

(n1): de verzameling van alle unieke 'minimale' varianten van meerplaastige geneste structuren voor n1 basiselementen tot maximaal twee diepteniveaus.

Voorbeeld.


Bijv. Stel n1

=

3;

tc *

(n1)

=

{ '(xxx)', '(x(xx))', '((xx)x)' }.
Maximaal aantal is 3.
Bijv. Stel n1

=

4;

tc *

(n1)

=

{ '(xxxx)', '(x(xxx))', '((xxx)x)', '(xx(xx))', '(x(xx)x)', '((xx)xx)', '((xx)(xx))', }.
Maximaal aantal is 7.
{ n1 (

t c*

(n1)

t m*

(n1) )n1 }.

Omvang.


tc(n1): het totale aantal elementen in verzameling

t c*

(n1).
De waarden tc(n1) zijn simpel afleidbaar met de functie voor A000225 (eerder M2655, N1059) in de OEIS.
{ n1 ( tc(n1)  

:=

2^(n1 -1 ) -1;
( tc(0)

=

0; t c(1)

=

1; (n1

>

1 ) ( tc(n1)

:=

A000225( n1 -1)

|

(offset 0 ) ) ) )n1 }.
Bijv. Voor n1

=

0,1,2,3, ..(t·(v,d)

=

16);
tc(n1)

=

{ 0, 1, 1, 3, 7, 15, 31, 63, 127, 255, 511,
1023, 2047, 4095, 8191, 16383, 32767 }.

(5.2)

Valentiervariatie bij symmetrische connectieven, tot diepteniveau twee.


Aan het toevoegen van negaties aan redeneervormen in standaard normaalvorm kleven een aantal complicaties.
(1)

Toevoeging van negaties leidt niet tot extra diepteniveau in in standaard normaalvorm formules.


Wanneer een redeneervorm al in standaard normaalvorm staat (zoals

CNF

of

DNF

) kunnen enkelvoudige elementen (atomen) - c.q. eindelementen (leaves) in een boomstructuur - in voorkomend geval voorzien zijn van negatie (prefix), zij het hoogstens één omdat negatief normaalvorm hier inherent is.
In principe vormt een negatie een connectief, al is die éénplaatsig. Ze voegt daardoor in principe een extra nest resp. diepteniveau toe in een boomstructuur. Daardoor zouden sommige varianten in de verzameling

tc*

(n1) buiten de klasse voor normaal vorm formules vallen.
Maar in logische formules voegen negaties in het algemeen niet een extra inbedding toe en dus evenmin een diepteniveau. Ze veranderen dus niets aan de geneste structuur van de standaard normaalvorm zoals we die in

tc*

(n1) verzameld hebben.
(2)

Er volgen dubbele negaties - ontoelaatbaar in standaard normaalvorm formules.


Zoals we bespraken bij de algemene meerplaatsige boomstructuren leidt het toevoegen van negaties in de verzamelingen van alle unieke 'kale' redeneervormen,

tm*

(n1), en dus ook haar deelverzameling

tm*

(n1 ), tot een explosie van doublures en dubbele negaties. De doublures behelzen overtolligheid die op zichzelf niet strikt foutief zijn, maar omdat in standaard normaalvorm negatief normaalvorm geldt, zijn dubbele negaties daarin ontoelaatbaar.
(3)

Er volgen buitengeplaatste negaties - ook ontoelaatbaar in standaard normaalvorm formules.


De uitdrukkingen van elementen uit

T

·(v,d) in de deelverzamelingen van

U

·(v,d) bestaan deels uit samengestelde c.q. geneste formules: de 'nesten' in de boomstructuren van de redeneringen. Deze kunnen in standaard normaalvorm (eveneens conform negatief normaalvorm) echter geen buitengeplaatste negatie hebben. Deze negatievarianten moeten dus strikt genomen worden uitgesloten van standaard normaalvorm formules.
Uit deze drie kanttekeningen volgt dat negatievarianten in standaard normaalvorm formules maar heel selectief toepasbaar zijn.

(5.2.1)

Valentievariatie bij (atomaire) basiselementen.


Met de bovenstaande opmerkingen in gedachten bekijken we hieronder de valentievariatie voor formules in normaal vorm notatie in de algemene situatie waarin basiselementen atomair van aard zijn.
(5.2.1a)

Totaal aantal (occurrences) van leaves:


Omvang.


Ac(n1): het totale aantal eindelementen in de verzameling

t c*

(n1).
Berekening analoog aan die van Am(n1).
De waarden Ac(n1) komen goeddeels overeen met reeks A058877 in de OEIS.
Ac(0)

=

0; Ac (1)

=

1; n1 ( (n1

>

1 ) ( Ac(n1)

:=

A058877(n1 )

|

(offset 1 ) ) ) )n1 }.
Bijv. Voor n1

=

0,1,2,3, ..(t·(v,d)

=

16);
Ac(n1)

=

{ 0, 1, 2, 9, 28, 75, 186, 441, 1016, 2295, 5110,
11253, 24564, 53235, 114674, 245745, 524272 }.
(5.2.1b)

Valentievariatie over leaves:


tcv*A

(n1): de verzameling

tc*

(n1) uitgebreid met alle unieke valentievariaties over eindelementen.

Voorbeeld.


Bijv. Stel n1

=

3;

tc v*A

(n1)

=

{ '(xxx)', '(x(xx))', '((xx)x)', '(xx¬x)', '(x(x¬x))', '((xx)¬x)', '(x¬xx)', '(x(¬xx))', '((x¬x)x)', '(x¬x¬x)', '(x(¬x¬x))', '((x¬x)¬x)', '(¬xxx)', '(¬x(xx))', '(¬(xx)x)', '(¬xx¬x)', '(¬x(x¬x))', '(¬(xx)¬x)', '(¬x¬xx)', '(¬x(¬xx))', '(¬(x¬x)x)', '(¬x¬x¬x)', '(¬x(¬x¬x))', '(¬(x¬x)¬x)' }.
Maximaal aantal is 24.
{ v

|

n1 (

tc*A

(n1)

tcv*A

(n1) )n1, v }.

Omvang.


tcvA(n1): het totale aantal elementen in verzameling

tcv* A

(n1).
Berekening analoog aan die van tmvA(n1).
De waarden tcvA(n1) komen goeddeels overeen - afgezien van de eerste twee waarden - met die van reeks A059153 in de OEIS.
{ tcvA(0)

=

0; tcvA(1)

=

2; n1 ( (n1

>

1 ) ( tcvA(n1)

:=

A059153(n1 -2 )

|

(offset 0 ) ) )n1 }.
Bijv. Voor n1

=

0,1,2,3, ..(t·(v,d)

=

16);
tcvA(n1)

=

{ 0, 2, 4, 24, 112, 480, 1984, 8064, 32512, 130560, 523264,
2095104, 8384512, 33546240, 134201344, 536838144, 2147418112 }.

(5.2.2)

Valentievariatie bij nesten.


Zoals gezegd zijn deze niet van toepassing (c.q. niet toelaatbaar) in het geval van normaal vorm formules.

(5.2.3)

Valentievariatie over basiselementen èn nesten.


Hierin telt uiteraard alleen de valentievariatie over basiselementen mee, zodat ze hieraan gelijk is.

(5.3)

Volgordevariatie bij symmetrische connectieven, tot diepteniveau twee.



(5.3.1)

Volgordevariatie bij basiselementen.


(5.3.1a)

Geldige permutaties (faculteiten) voor volgordes van leaves:


Gelijk aan de waarden F(n1) als vermeld voor de algemene meerplaatsige boomstructuren.
(5.3.1b)

Volgordevariatie over leaves:


tcv,o*A

(n1): de verzameling

tcv*A

(n1 ) uitgebreid met alle unieke volgordevariaties over eindelementen.
{ v

|

n1 (

tcv*A

(n1)

tcv,o* A

(n1) )n1, v }.

Voorbeeld.


Mutatis mutandis analoog aan die van

tmv,o*A

(n1).

Omvang.


tcv,o*A(n1): het totale aantal elementen in verzameling

tcv,o* A

(n1).
Berekening analoog aan die van tmv,o*A(n1 ).
De waarden tcv,oA(n1) komen niet voor als reeks in , maar zijn afleidbaar met behulp van de eerdergenoemde reeks A059153.
tcvA(0)

=

0; tcvA(1)

=

2; n1 ( (n1

>

1 ) ( tcvA(n1)

:=

A059153(n1 -2 )

*

P(n1)

|

(offset 0 ) ) )n1 }.
Bijv. Stel n1

=

3; tc v,o*A(n1)

:=

((tcv A(n1)

=

24 )

*

(P(n1)

=

6 )

=

) 144.
Bijv. Voor n1

=

0,1,2,3, ..(t·(v,d)

=

16);
tcv,oA(n1)

=

{ 0, 2, 8, 144, 2688, 57600, 1428480, 40642560, 1310883840, 47377612800, 1898820403200,
83629847347200, 4016194663219200, 208893134241792000, 11699443846663373000, 702009480673493000000, 4.492997795906165e+22 }.

(5.3.2)

Volgordevariatie bij nesten.


Zoals gezegd telt volgordevariatie niet voor nesten.

(5.3.3)

Volgordevariatie over nodes (leaves èn nesten):


Uiteraard is deze gelijk aan die bij eindelementen.

(5.4)

Connectiefvariatie bij symmetrische connectieven, tot diepteniveau twee.


In normaalvorm formules hebben we enkel te maken met twee symmetrische connectieven: conjunctie en disjunctie.
{ (

Cc*

=

{ '', '' } );
c1

:=

|

C c*

|

;

:=

2 }.

(5.4.1)

Connectiefvariatie bij basiselementen.


De connectiefvariatie is niet direct afhankelijk van de basiselementen.

(5.4.2)

Connectiefvariatie bij nesten.


(5.4.2a)

Connectiefvariatie per nest opgeteld:


Cc(n1,c1): de hoeveelheid connectiefvariatie van alle nesten in de elementen in een verzameling

tc*

(n1) opgeteld bij c1 connectiefsymbolen.

Omvang.


In normaalvorm formules gelden specifieke kenmerken voor connectieven: (a) Er zijn alleen symmetrische connectieven; (b) Het aantal mogelijke connectieven is beperkt tot twee; (c) Dit aantal is constant over verschillende bomen (of structuurvarianten); (d) En dus is het onafhankelijk van het aantal nesten; (e) Het nestingniveau is bovendien ook beperkt tot twee; (f) Daardoor zijn er voor het hoofdconnectief hoogstens twee opties en voor de andere precies één.
Hierdoor is de berekening van de connectiefvariatie bijzonder eenvoudig.
De waarden Cc(n1,c1) komen goeddeels overeen met reeks A000918 in de OEIS.
{ v

|

n1 ( (tc(n1)

:=

|

t c*

(n1)

|

);
m1 ( (m1

:=

tc(n1) );
c1 ( (c1

<

3 );
( ( i1 (Cc(n1,c1)[ i1]  

:=

c1 )i1 );
(Cc(n1,c1)

:=

(i1 := 1,

..

m1 ) Cc(n1,c1)[i1] i1;

:=

(i1 := 1,

..

m1 ) c1 i1;

:=

(m1 *c1 ) ) ) )c1 )m1 ) n1, v;
( Cc(0,2)

=

0; C c(1,2)

=

1; n1 ( (n1

>

1 ) Cc(n1,2)

:=

A000918(n1)

|

(offset 0 ) ) )n1 ) }.
Bijv. Stel n1

=

3; Cc( n1,c1)

:=

((n1

=

3 )

*

(c1

=

2 )

=

) 6.
Bijv. Voor n1

=

0,1,2,3, ..(t·(v,d)

=

16); c1

=

2;
Cc(n1,c1)

=

{ 0, 1, 2, 6, 14, 30, 62, 126, 254, 510, 1022,
2046, 4094, 8190, 16382, 32766, 65534 }.
(5.4.2b)

Connectiefvariatie over nesten:


tcv[,o],c*N

(n1,c1 ): de verzameling

tcv*N

( n1) uitgebreid met alle unieke connectiefvariaties over nesten.
Zoals we zagen tellen voor meerplaatsige geneste structuren in normaalvorm noch valentievariatie, noch volgordevariatie van de nesten mee. De connectiefvariatie over nesten valt hierdoor eenvoudig samen met de connectiefvariatie per nest opgeteld Cc(n1,c1).

(5.4.3)

Connectiefvariatie over nodes (leaves èn nesten):


(5.4.3a)

Connectiefvariatie per node opgeteld:


Uiteraard is deze eveneens gelijk aan Cc(n1,c1).
(5.4.3b)

Connectiefvariatie over nodes (leaves èn nesten):


tcv,o,c*K

(n1,c1 ): de verzameling

tcv,o*K

( n1) uitgebreid met alle unieke connectiefvariaties over (alleen) nesten bij c1 connectiefsymbolen.
{ v

|

n1 c1 (

tcv,o* K

(n1)

t cv,o,c*K

(n1,c1) )c1 , n1, v }.

Omvang.


tcv,o,c*K(n1,c1): het totale aantal elementen in verzameling

tcv,o,c* K

(n1,c1).
NB. De waarden tcv,o,cK(n1,c1) komen niet voor als reeks in de OEIS.
{ v

|

n1 ( (tc(n1)

:=

|

t c*

(n1)

|

);
m1 ( (m1

:=

tc(n1) );
c1 ( (c1

<

3 );
( ( i1 (Cc(n1,c1)[ i1]  

:=

c1 )i1 );
(Cc(n1,c1)

:=

(i1 := 1,

..

m1 ) Cc(n1,c1)[i1] i1;

:=

(i1 := 1,

..

m1 ) c1 i1;

:=

m1 *c1 );
(tcv,o,cK( n1,c1)

:=

tcv,oK(n1 ) *c1 ) ) ) )c1 )m1 )n1, v }.
Bijv. Stel n1

=

3; tc v,o,c*K(n1,c1)

:=

((tc v,oK(n1)

=

144 )

*

(c1

=

2 )

=

) 288.
Bijv. Voor n1

=

0,1,2,3, ..(t·(v,d)

=

16); c1

=

2;
tcv,o,cK(n1, c1)

=

{, 0, 2, 16, 288, 5376, 115200, 2856960, 81285120, 2621767680, 94755225600, 3797640806400,
167259694694400, 8032389326438400, 417786268483584000, 23398887693326746000, 1.404018961346986e+21, 8.98599559181233e+22 }.
NB. Deze reeks is nog steeds niet hyperexponentieel.

(5.5)

Deelverzamelingen per lengte bij symmetrische connectieven, tot diepteniveau twee.



(5.5.1)

Binomiaal coëfficiënten:


Gelijk aan de waarden B(t·(v,d), n1) als vermeld voor de algemene meerplaatsige boomstructuren.

(5.5.2)

Subsets (per lengte) over nodes (leaves èn nesten):


tcv,o,c,s*K

(n1,c1 ): de verzameling met alle unieke verzamelingen

tcv,o,c* K

(n1,c1) van 'minimale' syntactische varianten over eindelementen en nesten binnen meerplaatsige geneste structuren tot diepteniveau twee met elk n1 unieke basiselementen, inclusief valentievarianten, volgordevarianten en connectiefvarianten bij c1 connectiefsymbolen.
{ v

|

n1 c1 (

tcv,o,c* K

(n1,c1)

t cv,o,c,s*K

(n1,c1) ) c1, n1, v }.

Omvang.


tcv,o,c,s*K(n1,c1): het totale aantal elementen in verzameling

tcv,o,c,s* K

(n1,c1).
Berekening analoog aan die van tmv,o,c,s*K( n1,c1).
NB. De waarden tcv,o,c,sK(n1,c1) komen niet voor als reeks in de OEIS.
Bijv. Stel n1

=

3; tc v,o,c,sK(n1,c1)

:=

((tcv,o,cK(n1,c1)

=

288 )

*

(B(t·(v,d ), n1)

=

560 )

=

) 161280.
Bijv. Voor n1

=

0,1,2,3, ..(t·(v,d)

=

16); c1

=

2;
tcv,o,c,sK(n1, c1)

=

{ 0, 32, 1920, 161280, 9784320, 503193600, 22878535680, 929901772800, 33742150041600, 1083999780864000, 30411507577651200,
730590346425139200, 14618948574117888000, 233960310350807040000, 2.8078665231992095e+21, 2.2464303381551776e+22, 8.98599559181233e+22 }.

(5.5.3)

Totaal aantal varianten in alle subsets (per lengte) over nodes (leaves èn nesten):


Ten slotte kunnen de verzamelingen over de aantallen basislementen worden samengevoegd in een omvattende verzameling.

tcv,o,c,s*U

(v,d, c1): de verzameling van alle n1 verzamelingen

tcv,o,c,s *K

(n1,c1) bij c1 connectiefsymbolen.
{ v, d

|

n1 c1 (

t cv,o,c,s*K

(n1,c1)

tcv,o,c,s* U

(v,d,c1) )c1, n1 , d ,v }.

Omvang.


tcv,o,c,sU(v,d,c1): het totale aantal elementen in alle deelverzamelingen

tcv,o,c,s *K

(n1,c1) van

tc v,o,c,s*U

(v,d,c1).
Berekening analoog aan die van tmv,o,c,s*U( v,d,c1).
Bijv. Voor v

=

2; d

=

2; c1

=

2;
tcv,o,c,sU(v, d,c1)

=

1.1538146720234845e+23.

C.P. van der Velde © 2014, 2018.